/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ZhongJinTao
 * Date: 2025-09-22
 * Time: 10:02
 */

public class Sort {
    /**
     * 直接排序算法
     * @param array
     */
    public void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序
     */
    public void shellSort(int[] array) {
        int grap = array.length / 2;
        while(grap >= 1) {
            shell(array, grap);
            grap /= 2;
        }
    }
    public void shell(int[] array, int grap) {
        for (int i = grap; i < array.length; i += grap) {
            int j = i - grap;
            int tmp = array[i];
            for (; j >= 0; j -= grap) {
                if (array[j] > tmp) {
                    array[j + grap] = array[j];
                } else {
                    break;
                }
            }
            array[j + grap] = tmp;
        }
    }

    public void selectSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i + 1; j < array.length; j++) {
                if(array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            int tmp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tmp;
        }
    }

    /**
     * 冒泡排序
     */
    public void bubbleSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 快速排序
     */
    public void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private void quick(int[] array, int start, int end) {
        if(start >= end) {
            return;
        }
        int pivot = partitionHore(array, start, end);
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    private int partitionHore(int[] array, int left, int right) {
        int tmp = array[left];
        int cur = left;
        while(left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            int x = array[left];
            array[left] = array[right];
            array[right] = x;
        }
        int x = tmp;
        array[cur] = array[left];
        array[left] = x;

        return left;
    }
}
